class Solution(object):
    def isMatch(self, s, p):
       return self.match(s,0,p,0)

    def match(self,s,sIndex,p,pIndex):
        if len(p) == pIndex:
            return len(s) == sIndex

        flag = False

        # deal with '.' 
        if sIndex < len(s) and (s[sIndex] == p[pIndex] or p[pIndex] == '.'):
            flag = True
        
        # deal with '*'
        if(pIndex < len(p) - 1 and p[pIndex + 1] == '*'):
            # maybe empty or add 
            return self.match(s,sIndex,p,pIndex + 2) or (flag and self.match(s,sIndex+1,p,pIndex))
        else:
            # normal
            return flag and self.match(s,sIndex+1,p,pIndex+1)